#include <vector>
#include <algorithm>
using namespace std;
 
class Solution {
public:
    /**
     * return the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */
    vector<int> LIS(vector<int>& arr) {
        // write code here
        // 第一步：利用贪心+二分求最长递增子序列长度
        if(arr.size()==0)return arr;
        vector<int> res{arr[0]};
        vector<int> maxLen{1};
        for(int i=1;i<arr.size();i++)
        {
            if(arr[i]>=res.back())   ///一个是大于等于 一个是back（）  这里无论是写成大于等于 还是大于 都可以
            {
                res.emplace_back(arr[i]);
                maxLen.emplace_back(res.size());  ///注意这里是推入res.size()
            }
            else
            {
                //它的作用是返回有序数组begin..end中第一个大于等于val的元素的迭代器
                int pos=lower_bound(res.begin(),res.end(), arr[i])-res.begin();
                res[pos]=arr[i];
                maxLen.emplace_back(pos+1); ///存放以元素i结尾的最大递增子序列长度
                
            }
        }

                                   //注意这里 当maxLen中有两个相同的长度时，一定是后者更小，所以
                                       //这里只需要从后找到第一个==res.size（）的位置即可，由于
                                        //在遍历arr的过程中，只会增加res或者替换res的某个值，故最长一定是
                                            //res的size

       for (int i = arr.size() - 1, j = res.size(); j > 0; --i) {//maxLen数组里存放的不仅仅是以元素i结尾的最大递增子序列长度，还隐含了最长递增子序列的位置信息，理解了这一点，才能够填充最长递增子序列。
		if (maxLen[i] == j) {         //如果 maxLen元素最大为4   证明一定有1 2 3存在 ，这个 1 2 3的存在是将arr[i]推入res的顺序，arr的每个值在maxLen中都有着一个对应的值,从不同的最大值，向前遍历比自己小的值，
                                                //可以得到不同的递增子序列  
			res[--j] = arr[i];
		}
	}
        return res;
        
    }
       
};